package the_fourth_chapter;

/**
 * 插入排序法的原理是将一组无序的数字排成一排，左端第一个数字为已经完成排序的数字，其他数字为未排序的数字，
 * 然后从左到右依次将未排序的数字插入到已排序的数字中
 * 
 * 插入排序，原理：第一个数字已经完成排序，以后每一个数字和原来排完序的数组对比，然后插入相应位置
 * 
 * 
 * @author explorati
 *
 */
public class InsertSort {

	public static int[] insert_sort(int[] nums) {
		// 外层循环是控制遍数的
		// 由于第一个元素不用排序，所以只需要nums.length - 1遍重排
		for (int i = 1; i < nums.length; i++) {
			// j是从比i小一的位置
			for (int j = i; j > 0; j--) {
				// 注意此处都为j，i只是用来控制j的开始位置的
				if (nums[j] < nums[j - 1]) {
					int temp = nums[j];
					nums[j] = nums[j - 1];
					nums[j - 1] = temp;
				}
			}
		}
		return nums;
	}

	public static void main(String[] args) {
		int[] nums = { 5, 5, 6, 9, 2, 3, 4, 1 };
		System.out.println("插入排序前的数组为：");
		for (int i = 0; i < nums.length; i++) {
			System.out.print(nums[i] + "\t");
		}

		System.out.println();

		int[] num = insert_sort(nums);

		System.out.println("插入排序后的结果为：");
		for (int i = 0; i < num.length; i++) {
			System.out.print(num[i] + "\t");
		}
	}
}
